﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace P2PFileScheduling
{
    class FlowCalc
    {
        static int flow = 0;

        public static void PrintPath(List<DirectedEdge> path)
        {
            if (path.Count == 0)
                return;

            Console.Write("{0}/{1} => {2}/{3}", path[0].From.name, path[0].From.number, path[0].To.name, path[0].To.number);

            for (int i = 1; i < path.Count; ++i)
                Console.Write(" => {0}/{1}", path[i].To.name, path[i].To.number);

            Console.WriteLine();
        }

        public static void PrintPath(Digraph g, List<Vertex> path)
        {
            foreach (Vertex v in path)
            {
                if (v.number != g.superSource.number)
                    Console.Write("{0} => ", v.number);
                else
                    Console.WriteLine("{0}", v.number);
            }
        }

        public static int FordFulkerson(Digraph Graph, int type)
        {
            BreadthFirstDirectedPaths bfs_dir = new BreadthFirstDirectedPaths(Graph, Graph.superSource.number, type);

            List<DirectedEdge> path = bfs_dir.EdgePathTo(Graph.superSink.number);
            Console.WriteLine(Graph.toString());
            PrintPath(path);

            while (path != null)
            {
                flow = Augment(path, Graph);
                UpdatePieces(path, type);
                bfs_dir = new BreadthFirstDirectedPaths(Graph, Graph.superSource.number, type);
                path = bfs_dir.EdgePathTo(Graph.superSink.number);
                Console.WriteLine(Graph.toString());
                Console.WriteLine("Flow: {0}", flow);
                PrintPath(path);
            }

            return flow;
        }

        public static void UpdatePieces(List<DirectedEdge> path, int type)
        {
            path[1].To.pieces[type] = true;
            path[1].valid = false;
        }

        #region Vertex flow methods
        //public static int Augment(List<Vertex> path, Digraph g)
        //{
        //    int b = Bottleneck(path, g);
        //    foreach (Vertex v in path)
        //    {
        //        if (e.From == g.superSource || e.To == g.superSink || e.capacity > e.flow)
        //        {
        //            Graph.changeEdge(e, b, e.type);
        //            DirectedEdge otherWay = Graph.getEdge(e.to().number, e.from().number);
        //            otherWay = new DirectedEdge(Graph, e.to(), e.from(), e.ID + Graph.V, e.type);
        //            Graph.changeEdge(otherWay, -b, e.type);
        //        }
        //    }


        //    foreach (DirectedEdge e in Graph.adj[Graph.superSink.number])
        //    {
        //        if (e.flow < 0) flow -= e.flow;
        //    }
        //    return flow;
        //}

        //public static int Bottleneck(List<Vertex> path, Digraph g)
        //{
        //    int b = int.MaxValue;
        //    foreach (Vertex v in path)
        //    {
        //        int tryb = v.capacity - edge.flow;
        //        if (tryb < b && tryb >= 0) b = tryb;
        //    }
        //    return b;
        //}
        #endregion

        public static int Augment(List<DirectedEdge> P, Digraph Graph)
        {
            int b = Bottleneck(P, Graph);

            foreach (DirectedEdge e in P)
            {
                if (e.From == Graph.superSource || e.To == Graph.superSink || e.capacity > e.flow)
                {
                    Graph.changeEdge(e, b, e.type);
                    DirectedEdge otherWay = Graph.getEdge(e.To.number, e.From.number);
                    otherWay = new DirectedEdge(Graph, e.To, e.From, e.ID + Graph.V, e.type);
                    Graph.changeEdge(otherWay, -b, e.type);
                }
            }


            foreach (DirectedEdge e in Graph.adj[Graph.superSink.number])
                if (e.flow < 0) flow -= e.flow;

            return flow;
        }

        public static int Bottleneck(List<DirectedEdge> P, Digraph Gres)
        {
            // Alternative: P.Min(e => e.capacity - e.flow)

            int b = int.MaxValue;
            foreach (DirectedEdge edge in P)
            {
                int tryb = edge.capacity - edge.flow;
                if (tryb < b && tryb >= 0) b = tryb;
            }
            return b;
        }
    }
}
